Pascal's Triangle

LeetCode 118 | Difficulty: Easy

Easy

Problem Description

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

- `1 <= numRows <= 30`

Topics: Array, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 216 ms)

Metric	Value
Runtime	216 ms
Memory	25.2 MB
Date	2019-12-15

Solution

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
            IList<IList<int>> rows = new List<IList<int>>();
    for (int i = 0; i < numRows; i++)
    {
        rows.Add(new List<int>());
        for (int j = 0; j <= i; j++)
        {
            if (j == 0 || j == i)
            {
                rows[i].Add(1);
            }
            else
            {
                rows[i].Add(rows[i-1][j-1] + rows[i-1][j]);
            }
        }
    }
    
    return rows;
    }
}

📜 1 more C# submission(s)

Submission (2017-11-11) — 522 ms, N/A

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
    IList<IList<int>> rows = new List<IList<int>>();
    if(numRows==0) return rows;
    rows.Add(new List<int>() { 1 });
    if(numRows==1) return rows;
    rows.Add(new List<int>() { 1,1 });
    if(numRows==2) return rows;
    for (int i = 2; i < numRows; i++)
    {
        var row = new int[i+1];
        row[0]=1;
        row[i]=1;
        for (int j = 1; j < i; j++)
        {
            row[j] = rows[i-1][j-1]+rows[i-1][j];
        }
        rows.Add(row);
    }
    return rows;
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.